12.2. Král

1. Definujte pojem podgrafu. Kolik podgrafů má K3?

2. Popište problém minimální kostry, algoritmus pro jeho řesení a dokažte jeho správnost.

3. Mohou mít dva grafy G1 a G2 stejné skóre, jestliže
   a. G1 je 2-souvislý, G2 není souvislý
   b. G1 je strom, G2 je 2-souvislý
   c. G1 není rovinný, G2 je kružnice
   d. G1 není rovinný, G2 je strom

na většinu u trojky je odpověď ano, myslím kromě b

4. Které z následujících výroků jsou správné?
   a. Grafy G a H jsou izomorfní, právě když existuje bijekce f: E(G) -> E(H)
   b. Jestliže jsou grafy G a H izomorfní, pak existuje bijekce f: V(G) -> V(H) taková, že každý vrchol u z V(G) má stejný stupeň jako f(u).

1. definice souvisleho grafu + nejvetsi mozny pocet hran grafu s n vrcholy a t komponentami, ktery nemá kruznici.

2. Veta o max. poctu hran v n-vrcholovém grafu bez K_3 + dukaz

3. pocet permutaci pismen A,D,K,O,P,S,T,V bez slov KOP, PAST, VODA

4. Dokázte: má-li souvisly G vsechny stupne sudé, neobsahuje most.
   (most= hrana e take, ze G\e je nesouvisly)